// Copyright (c) 2016, Stefan Cloudt
// Permission to use, copy, modify, and/or distribute this software for any purpose
// with or without fee is hereby granted, provided that the above copyright notice
// and this permission notice appear in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
// OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

//! File containing the implementation of a sorted array.

use std::cmp::Ordering;

/// A sorted array that maintains its elements in sorted order.
pub struct SortedArray<T> {
    data: Vec<T>,
    equ_func: Box<dyn Fn(&T, &T) -> bool>,
    cmp_func: Box<dyn Fn(&T, &T) -> Ordering>,
}

impl<T> SortedArray<T> {
    /// Creates a new `SortedArray` with the specified initial capacity.
    ///
    /// # Arguments
    ///
    /// * `capacity` - The initial capacity of the array. If 0, a default of 16 is used.
    /// * `equ_func` - A closure to determine if two values are equal.
    /// * `cmp_func` - A closure to determine the order of two values.
    ///
    /// # Returns
    ///
    /// A new `SortedArray` or `None` if the capacity is invalid.
    pub fn new(
        capacity: usize,
        equ_func: Box<dyn Fn(&T, &T) -> bool>,
        cmp_func: Box<dyn Fn(&T, &T) -> Ordering>,
    ) -> Option<Self> {
        if capacity == 0 {
            return None;
        }
        Some(SortedArray {
            data: Vec::with_capacity(capacity),
            equ_func,
            cmp_func,
        })
    }

    /// Returns the length of the sorted array.
    pub fn len(&self) -> usize {
        self.data.len()
    }

    /// Clears the sorted array, removing all elements.
    pub fn clear(&mut self) {
        self.data.clear();
    }

    /// Inserts a new element into the sorted array while maintaining the sorted order.
    ///
    /// # Arguments
    ///
    /// * `data` - The element to insert.
    ///
    /// # Returns
    ///
    /// `true` if the insertion was successful, `false` otherwise.
    pub fn insert(&mut self, data: T) -> bool {
        let index = self.find_insert_index(&data);
        self.data.insert(index, data);
        true
    }

    /// Removes the element at the specified index.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the element to remove.
    pub fn remove(&mut self, index: usize) {
        if index < self.data.len() {
            self.data.remove(index);
        }
    }

    /// Removes a range of elements from the sorted array.
    ///
    /// # Arguments
    ///
    /// * `index` - The starting index of the range to remove.
    /// * `length` - The number of elements to remove.
    pub fn remove_range(&mut self, index: usize, length: usize) {
        if index + length <= self.data.len() {
            self.data.drain(index..index + length);
        }
    }

    /// Returns the element at the specified index.
    ///
    /// # Arguments
    ///
    /// * `index` - The index of the element to retrieve.
    ///
    /// # Returns
    ///
    /// A reference to the element or `None` if the index is out of bounds.
    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index)
    }

    /// Finds the index of the first occurrence of the specified element.
    ///
    /// # Arguments
    ///
    /// * `data` - The element to search for.
    ///
    /// # Returns
    ///
    /// The index of the element or `None` if not found.
    pub fn index_of(&self, data: &T) -> Option<usize> {
        let (left, right) = self.binary_search(data);
        for index in left..=right {
            if (self.equ_func)(data, &self.data[index]) {
                return Some(index);
            }
        }
        None
    }

    /// Finds the index where the element should be inserted to maintain the sorted order.
    fn find_insert_index(&self, data: &T) -> usize {
        let (mut left, mut right) = (0, self.data.len());
        while left < right {
            let mid = (left + right) / 2;
            match (self.cmp_func)(data, &self.data[mid]) {
                Ordering::Less => right = mid,
                Ordering::Greater => left = mid + 1,
                Ordering::Equal => return mid,
            }
        }
        left
    }

    /// Performs a binary search to find the range of indices where the element could be located.
    fn binary_search(&self, data: &T) -> (usize, usize) {
        let mut left = 0;
        let mut right = self.data.len();
        while left < right {
            let mid = (left + right) / 2;
            match (self.cmp_func)(data, &self.data[mid]) {
                Ordering::Less => right = mid,
                Ordering::Greater => left = mid + 1,
                Ordering::Equal => {
                    left = self.first_index(data, left, mid);
                    right = self.last_index(data, mid, right);
                    break;
                }
            }
        }
        (left, right)
    }

    /// Finds the first index of the range where the element equals the given data.
    fn first_index(&self, data: &T, mut left: usize, right: usize) -> usize {
        while left < right {
            let mid = (left + right) / 2;
            if (self.cmp_func)(data, &self.data[mid]) == Ordering::Greater {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }

    /// Finds the last index of the range where the element equals the given data.
    fn last_index(&self, data: &T, left: usize, mut right: usize) -> usize {
        while left < right {
            let mid = (left + right) / 2;
            if (self.cmp_func)(data, &self.data[mid]) == Ordering::Less {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        right
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_and_get() {
        let mut array = SortedArray::new(
            16,
            Box::new(|a, b| a == b),
            Box::new(|a, b| a.cmp(b)),
        )
        .unwrap();

        assert!(array.insert(5));
        assert!(array.insert(3));
        assert!(array.insert(8));

        assert_eq!(array.get(0), Some(&3));
        assert_eq!(array.get(1), Some(&5));
        assert_eq!(array.get(2), Some(&8));
    }

    #[test]
    fn test_index_of() {
        let mut array = SortedArray::new(
            16,
            Box::new(|a, b| a == b),
            Box::new(|a, b| a.cmp(b)),
        )
        .unwrap();

        array.insert(5);
        array.insert(3);
        array.insert(8);

        assert_eq!(array.index_of(&3), Some(0));
        assert_eq!(array.index_of(&5), Some(1));
        assert_eq!(array.index_of(&8), Some(2));
        assert_eq!(array.index_of(&10), None);
    }

    #[test]
    fn test_remove() {
        let mut array = SortedArray::new(
            16,
            Box::new(|a, b| a == b),
            Box::new(|a, b| a.cmp(b)),
        )
        .unwrap();

        array.insert(5);
        array.insert(3);
        array.insert(8);

        array.remove(1);
        assert_eq!(array.get(0), Some(&3));
        assert_eq!(array.get(1), Some(&8));

        array.remove_range(0, 2);
        assert_eq!(array.len(), 0);
    }
}
